Problem statement: zenit13kkf

Po počiatočných povinnostiach sa Maroško konečne dostal k oddychu v Grasalkovičovom paláci. Rád by si nový domov upravil podľa svojho vkusu. Napríklad obrazy historických štátnikov na chodbe sú zavesené bez akéhokoľvek systému. Maroško by bol rád, keby boli tieto portréty zoradené podľa roku narodenia vyobrazených ľudí. Človek idúci po chodbe z jedného konca na druhý by tak mal pekný chronologický prierez históriou.

Maroško nám trochu uľahčil úlohu a o každom obraze zistil, na ktorom mieste by mal v správnom poradí visieť. Aby nevznikol chaos, bude pri preusporiadavaní postupovať systematicky. V každom kroku zvolí dvojicu visiacich obrazov, oba zvesí a zavesí na opačné miesta. Toto opakuje až pokým nie sú obrazy správne usporiadané. Koľko najmenej takýchto operácii potrebuje?

Na prvom riadku vstupu je počet obrazov N, kde 2 ≤ N ≤ 100,000. Na druhom riadku je N medzerou oddelených celých čísel. V tejto postupnosti je každé z čísel 1 až N práve raz. Táto postupnosť označuje aktuálne usporiadanie obrazov. Ak je napríklad na piatom mieste tejto postupnosti 1, potom to znamená, že obraz, ktorý je v súčasnosti zavesený ako piaty by mal visieť na prvom mieste.

Maroškova operácia vymení pozície dvoch čísel v tejto postupnosti. Na výstup vypíšte jediné číslo - minimálny počet krokov potrebných na transformáciu vstupnej postupnosti na usporiadanie 1,2,... N−1, N.

5
5 4 1 2 3 

3 

4
1 2 3 4 

0 

6
2 3 4 5 6 1 

5